package com.company.nowcoder;

import java.math.BigInteger;
import java.util.Scanner;

/**
 * @author jrue
 * @description https://www.nowcoder.com/practice/1e6ac1a96c3149348aa9009709a36a6f?tpId=98&tqId=32934&tPage=6&rp=6&ru=/ta/2019test&qru=/ta/2019test/question-ranking
 * @date 2019/12/10 9:31
 * 在你面前有一个n阶的楼梯(n>=100且n<500)，你一步只能上1阶或3阶。
 * 请问计算出你可以采用多少种不同的方式爬完这个楼梯（到最后一层为爬完）。
 *
 * 输入:
 * 100
 * 输出:
 * 24382819596721629
 */
public class ClimbStair {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        BigInteger[] dp = new BigInteger[n + 1];

        for (int i = 1; i < dp.length; i++) {
            if (i == 1) dp[i] = new BigInteger("1");
            else if (i == 2) dp[i]  = new BigInteger("1");
            else if (i == 3) dp[i] = new BigInteger("2");
            else {
                dp[i] = dp[i - 1].add(dp[i - 3]);
            }
        }
        System.out.println(dp[n]);
    }

}
